package algorithm.graph.adjacencymatrix;

import java.util.*;

public class Floyd {
    AdjacencyMatrixGraph graph;
    int[][] transferMatrix;
    int[][] minPathLengthMatrix;

    public Floyd(AdjacencyMatrixGraph graph) {
        this.graph = graph;
    }


    public void buildPathMatrix() {
        this.transferMatrix = initTransfer(graph.getNodeCount());
        this.minPathLengthMatrix = initPathLength(graph.getNodeCount(), graph.getGraphData());
        int nodeCount = graph.getNodeCount();
        for (int k = 0; k < nodeCount; k++) {
            for (int i = 0; i < nodeCount; i++) {
                for (int j = 0; j < nodeCount; j++) {
                    if (minPathLengthMatrix[i][k] != -1 && minPathLengthMatrix[k][j] != -1) {
                        if (minPathLengthMatrix[i][j] == -1 ||
                                minPathLengthMatrix[i][j] > minPathLengthMatrix[i][k] + minPathLengthMatrix[k][j]) {
                            minPathLengthMatrix[i][j] = minPathLengthMatrix[i][k] + minPathLengthMatrix[k][j];
                            transferMatrix[i][j] = k;
                        }
                    }
                }
            }
        }
    }

    private int[][] initPathLength(int nodeCount, int[][] graphData) {
        int[][] pathLength = new int[nodeCount][nodeCount];
        for (int i = 0; i < nodeCount; i++) {
            for (int j = 0; j < nodeCount; j++) {
                pathLength[i][j] = graphData[i][j];
            }
        }
        return pathLength;
    }

    private int[][] initTransfer(int nodeCount) {
        int[][] transfer = new int[nodeCount][nodeCount];
        for (int i = 0; i < transfer.length; i++) {
            Arrays.fill(transfer[i], -1);
        }
        return transfer;
    }

    public List<Integer> findShortestPath(int from, int to) {
        if (minPathLengthMatrix[from][to] == -1) {
            if (from == to) {
                return List.of(from);
            } else {
                return List.of();
            }
        } else {
            List<Integer> transferList = findShortestPathSupport(from, to);
            List<Integer> result = new ArrayList<>();
            result.add(from);
            result.addAll(transferList);
            result.add(to);
            return result;
        }
    }

    private List<Integer> findShortestPathSupport(int from, int to) {
        if (transferMatrix[from][to] == -1) {
            return List.of();
        } else {
            int transfer = transferMatrix[from][to];
            List<Integer> result = new ArrayList<>();
            result.addAll(findShortestPathSupport(from, transfer));
            result.add(transfer);
            result.addAll(findShortestPathSupport(transfer, to));
            return result;
        }
    }
}
